package top.zz;

/**
 * 
 * @author game
 *
 */
public class LinkedTest {

	public static void main(String[] args) {
		DoublePointLinked linkedList = new DoublePointLinked();
		linkedList.addHead("A");
		linkedList.addHead("B");
		linkedList.addHead("C");
		linkedList.addHead("D");
		linkedList.display();

		linkedList.remove("C");
		linkedList.display();
		
		linkedList.addTail("NULL");
		
		linkedList.display();
	}

}

/**
 * 单端单向链
 * 
 * @author game
 *
 */
class SingleLinkedList {

	int size;

	Node head;

	class Node {
		Object data;
		Node next;

		public Node(Object data) {
			this.data = data;
		}

		public void setNext(Node next) {
			this.next = next;
		}
	}

	/**
	 * 头部增加
	 * 
	 * @param data
	 * @return
	 */
	public Object addHead(Object data) {
		if (size == 0) {
			head = new Node(data);
		} else {
			Node newHead = new Node(data);
			newHead.setNext(head);
			head = newHead;
		}

		size++;

		return data;
	}

	public Object getHead() {
		return head.data;
	}
	
	/**
	 * 删除头部元素
	 * 
	 * @return
	 */
	public Object removeHead() {
		Object data = null;
		if (head != null) {
			data = head.data;
			head = head.next;
			size--;
		}

		return data;
	}

	/**
	 * 查找指定元素
	 * 
	 * @param object
	 * @return {@link top.zz.singleLinkedList.Node}
	 */
	@SuppressWarnings(value = { "unused" })
	private Node find(Object object) {
		Node current = head;

		while (current != null) {
			if (current.data.equals(object)) {
				return current;
			} else {
				current = current.next;
			}
		}

		return null;
	}

	public boolean remove(Object object) {
		if (object == null) {
			return false;
		}

		Node current = head;
		Node previous = null;

		if (current.equals(head) && current.data.equals(object)) {
			head = current.next;
			size--;
			return true;
		}
		while (null != current) {
			if (object.equals(current.data)) {
				previous.next = current.next;
				size--;
				return true;
			} else {
				previous = current;
				current = current.next;
			}
		}

		return false;
	}

	public void display() {
		Node node = head;
		System.out.print("[ ");
		while (null != node) {

			if (node.next != null) {
				System.out.print(node.data + " -> ");
			} else {
				System.out.print(node.data + " ]");
			}
			node = node.next;
		}
		System.out.println();
	}

	public boolean isEmpty() {
		return size == 0;
	}
}

class DoublePointLinked extends SingleLinkedList {
	Node tail;

	public DoublePointLinked() {
		super();
		this.tail = null;
	}

	@Override
	public Object addHead(Object data) {

		if (size == 0) {
			super.addHead(data);
			tail = head;
		} else {
			super.addHead(data);
		}

		return data;
	}

	public Object addTail(Object data) {

		if (size == 0) {
			addHead(data);
		} else {
			Node newTail = new Node(data);
			tail.next = newTail;
			tail = newTail;
			size++;
		}

		return data;
	}

	@Override
	public Object removeHead() {
		Object temp = null;
		if (size > 1) {
			return super.removeHead();
		} else if(size == 1) {
			temp = head.data;
			head = null;
			tail = null;
		}
		return temp;
	}
}